package week09

// 253. 普通平衡树
// https://www.acwing.com/problem/content/255/

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	var n = 0
	fmt.Scanf("%d", &n)
	treap := NewTreap()
	for i := 0; i < n; i++ {
		var opt, x = 0, 0
		fmt.Scanf("%d%d", &opt, &x)
		switch opt {
		case 1:
			treap.Insert(x)
		case 2:
			treap.Remove(x)
		case 3:
			fmt.Println(treap.GetRankByVal(x))
		case 4:
			fmt.Println(treap.GetValByRank(x))
		case 5:
			fmt.Println(treap.GetPre(x))
		case 6:
			fmt.Println(treap.GetNext(x))
		}
	}
}

func init() {
	rand.Seed(time.Now().Unix())
}

type Node struct {
	Left, Right *Node
	Val, weight int
	cnt, size   int
}

func NewNode(val int) *Node {
	return &Node{
		Val:    val,
		weight: rand.Int(),
		cnt:    1,
		size:   1,
	}
}

type Treap struct {
	root *Node
}

func NewTreap() *Treap {
	root := NewNode(-1e9)
	root.Right = NewNode(1e9)
	return &Treap{
		root: root,
	}
}

func (t *Treap) Insert(val int) {
	t.root = t.insert(t.root, val)
}

func (t *Treap) Remove(val int) {
	t.root = t.remove(t.root, val)
}

func (t *Treap) GetRankByVal(val int) int {
	return t.getRankByVal(t.root, val) - 1
}

func (t *Treap) GetValByRank(rank int) int {
	return t.getValByRank(t.root, rank+1)
}

func (t *Treap) GetPre(target int) int {
	var ans int = -1e9
	var p = t.root
	for p != nil {
		if p.Val == target {
			// 如果有左节点，左节点一直往右
			if p.Left != nil {
				l := p.Left
				for l.Right != nil {
					l = l.Right
				}
				return l.Val
			}
			return ans
		}
		// 没有左节点，前驱在经过的点中（小于val的最大值）
		if p.Val < target && p.Val > ans {
			ans = p.Val
		}
		if p.Val > target {
			p = p.Left
		} else {
			p = p.Right
		}
	}
	return ans
}

func (t *Treap) GetNext(target int) int {
	var ans int = 1e9
	var p = t.root
	for p != nil {
		if p.Val == target {
			if p.Right != nil {
				r := p.Right
				for r.Left != nil {
					r = r.Left
				}
				return r.Val
			}
			return ans
		}
		// > target 最小值
		if p.Val > target && p.Val < ans {
			ans = p.Val
		}
		if p.Val > target {
			p = p.Left
		} else {
			p = p.Right
		}
	}
	return ans
}

func (t *Treap) insert(p *Node, val int) *Node {
	if p == nil {
		p = NewNode(val)
	} else if p.Val == val {
		p.cnt++
		t.update(p)
		return p
	} else if p.Val > val {
		p.Left = t.insert(p.Left, val)
		if p.weight < p.Left.weight {
			// 左孩子绕p右旋
			p = t.zig(p)
		}
	} else {
		p.Right = t.insert(p.Right, val)
		if p.weight < p.Right.weight {
			// 右孩子绕p左旋
			p = t.zag(p)
		}
	}
	t.update(p)
	return p
}

func (t *Treap) remove(p *Node, val int) *Node {
	if p == nil {
		return nil
	}
	if p.Val == val {
		if p.cnt > 1 {
			p.cnt--
			t.update(p)
			return p
		}
		// 叶子节点直接删除
		if p.Left == nil && p.Right == nil {
			return nil
		}
		// 左节点绕p右旋
		if p.Right == nil || p.Left != nil && p.Left.weight > p.Right.weight {
			p = t.zig(p)
			p.Right = t.remove(p.Right, val)
		} else { // 右节点绕p左旋
			p = t.zag(p)
			p.Left = t.remove(p.Left, val)
		}
		if p != nil {
			t.update(p)
		}
		return p
	}
	if p.Val > val {
		p.Left = t.remove(p.Left, val)
	} else {
		p.Right = t.remove(p.Right, val)
	}
	t.update(p)
	return p
}

func (t *Treap) getRankByVal(p *Node, val int) int {
	if p == nil {
		return 0
	}
	var leftSize = 0
	if p.Left != nil {
		leftSize = p.Left.size
	}
	if p.Val == val {
		return leftSize + 1
	}
	if p.Val > val {
		return t.getRankByVal(p.Left, val)
	}
	return leftSize + p.cnt + t.getRankByVal(p.Right, val)
}

func (t *Treap) getValByRank(p *Node, rank int) int {
	if p == nil {
		return 1e9
	}
	var leftSize = 0
	if p.Left != nil {
		leftSize = p.Left.size
	}
	if leftSize >= rank {
		return t.getValByRank(p.Left, rank)
	}
	if leftSize+p.cnt >= rank {
		return p.Val
	}
	return t.getValByRank(p.Right, rank-leftSize-p.cnt)

}

// 左节点绕p右旋
func (t *Treap) zig(p *Node) *Node {
	q := p.Left
	p.Left = q.Right
	q.Right = p
	t.update(p)
	t.update(q)
	return q
}

// 右节点绕p左旋
func (t *Treap) zag(p *Node) *Node {
	q := p.Right
	p.Right = q.Left
	q.Left = p
	t.update(p)
	t.update(q)
	return q
}

func (t *Treap) update(p *Node) {
	var leftSize, rightSize = 0, 0
	if p.Left != nil {
		leftSize = p.Left.size
	}
	if p.Right != nil {
		rightSize = p.Right.size
	}
	p.size = leftSize + rightSize + p.cnt
}
